1. Field of the Invention
This invention relates to the field of image processing systems, and in particular to the communication and presentation of wavelet encoded images.
2. Description of Related Art
There are several ways to process information hierarchically. Wavelets offer a highly efficient framework for representing and processing hierarchically structured information or processes. In general terms, a wavelet representation of a function consists of a coarse overall approximation together with detail coefficients that influence the function at various scales. In image processing, wavelet encodings are used to encode images via a hierarchy of terms.
A variety of alternative wavelet encoding techniques are common in the art. An example wavelet encoding technique that uses straightforward average and difference terms is presented herein for ease of understanding. Two image elements, such as two pixel values a, b, can be encoded as two other values, Q, Z, where Q=(a+b)/2, the average term, and Z=(axe2x88x92b), the difference term. To decode the values a, b, from the encodings Q, Z: a=Q+Z/2, and b=Qxe2x88x92Z/2. Four pixel values a0, b0, a1, a2 can be represented as two pair of encodings Q0, Z0, Q1, Z1, and the two average terms Q0, Q1 can be represented as encodings Q, Y, where Q is the average of Q0 and Q1, and Y is the difference between Q0 and Q1.
The use of wavelets offer a number of advantages and efficiencies. If all four pixel values are equal, the Q term will equal this value, and each of the difference terms Y, Z0, and Z1 will be zero. Techniques are common in the art for very efficient encodings and representations of zero-laden encodings. Note also that, because the Q term represents the average of the pixel values, the Q term can be used in place of the four pixel values until the difference terms Y, Z0, and Z1 are received and processed. That is, as the difference terms in a wavelet encoding are being processed, the average terms can be displayed, thereby presenting an image that iteratively becomes more and more detailed.
FIG. 1 illustrates an example wavelet encoding of a sixteen element block A 110, each element 111, 112, . . . representing, for example, the value of a picture element (pixel) for rendering on a display screen. An index block 110xe2x80x2 is shown in FIG. 1 for ease of reference to the individual elements of block A 110. That is, the upper left element 111 of block A 110 is referenced as a0, the next lower element 112 is referenced as a1, and so on.
Blocks B 120 and Z 130 represents the average and difference blocks corresponding to a pair-wise encoding of the individual elements of the block A 110. That is, cell b0 121 of block B 120 represents the average of elements a0 111 and a1 112, and cell Z0131 of block Z 130 represents the difference of elements a0 111 and a1 112.
Blocks C 140 and Y 150 represents the average and difference blocks corresponding to a pair-wise encoding of the individual elements of the block B 120. That is, cell c0 141 of block C 140 represents the average of elements b0 121 and b1 122, and cell Y0151 of block Y 150 represents the difference of elements b0 121 and b1 122.
In like manner, blocks D 160 and X 170 represent the average and difference blocks corresponding to block C 140, and blocks E 180 and W 190 represent the average and difference blocks corresponding to block D 160.
As discussed above, each of the cells of blocks E 180, D 160, C 140, and B 120 represent the average value of the pixel elements of block A 110 contained within the respective cell. The single cell of block E 180, for example, has a value of 0.625, which is the average of all the pixel elements of block A. The upper left cell c0 141 of block C 140 has a value of 0, which is the average of all the pixel elements of block A in the upper left region ((2+0+(xe2x88x923)+1)/4). Thus, a display of blocks E 180, D 160, C 140, B 120, and A 110, in that order, will present a progressively more detailed, or finer-resolution, view of the image represented by the pixel elements of block A 110.
Note that the values of the cells of the block D 160 can be determined from the value of block E 180 and W 190, as discussed above, and as illustrated in FIG. 2. That is, d0=E+W/2, and d1=Exe2x88x92W/2. In like manner, the value of the cells of block C 140 can be determined from the value of this determined block D 160 and the difference block X 170; block B 120 can be determined from C 140 and Y 150; and block A 110 can be determined from B 120 and Z 130. Thus, the communication of blocks E 180, W 190, X 170, Y 150, and Z 130 is sufficient to communicate the sixteen element values a0-a15 of block A 110. Note also that the blocks E 180 and W 190 contain one value each; X 170 contains two values; Y 150 contains four values; and Z 130 contains eight values. Thus, the communication of blocks E 180, W 190, X 170, Y 150, and Z 130 require the communication of a total of sixteen values, the same number of values contained in the original block A 110.
Wavelets are commonly used to communicate images so that increasingly more detailed views of the image can be displayed while the more detailed information is being received. This provides the advantage of providing a distraction to the viewer while the image is being downloaded, as well as to allow the user to terminate the transmission when it is determined that a sufficient amount of detail has been communicated.
It is an object of this invention to exploit the progressive-resolution characteristics of wavelets to provide a rendering of an image, or images, that takes advantage of the human perceptive system.
As is known in the field of art, a human""s visual field is typically drawn to a focal point, or focal area, within a scene. As the radial distance from that focal area increases, the human perceives less and less detail. This phenomenon is termed foveation. Artists purposely add a detail or feature to define such a focal point, to either bring the user""s attention specifically to the feature, or to put the scene in proper perspective, or to diminish the distracting effects caused by a lack of focus. Commercial artists take advantage of this phenomenon in advertising to draw the viewer""s attention to the item being advertized. Internet advertising is becoming increasingly popular, with multiple advertisers typically vying for a viewer""s attention. Copending U.S. patent application xe2x80x9cEVOLVING ADVERTISEMENTS VIA AN EVOLUTIONARY ALGORITHMxe2x80x9d, U.S. Ser. No. 09/277,650, filed Mar. 26, 1999, for J. David Schaffer, provides a method for evaluating and evolving an advertising campaign based on measures of viewer interest, including the number of users who select the advertised page, and so on, and is included by reference herein.
In like manner, computer applications are being developed to assist users in locating items of potential interest among a multitude of available items. Copending U.S. patent application xe2x80x9cDEVICE AND METHOD FOR A LATTICE DISPLAYxe2x80x9d, U.S. Ser. No. 09/282,321, filed Mar. 31, 1999, for Jacquelyn Martino, Nevenka Dimitrova, and Kaushal Kurapati, presents a system for displaying multiple images in a hierarchical manner, depending upon a measure of each image""s potential interest to the viewer, and is incorporated by reference herein. In this referenced patent application, images having a high potential interest to the user are presented with more prominence than others, where prominence is effected via the image""s size, location, resolution, brightness, border trim, and so on.
The expressed object of this invention, and others are achieved by providing a method and apparatus for rendering wavelets in a hierarchical manner. Different images, or sub-images, are rendered at different wavelet decoding rates, the more rapidly decoded wavelets forming a focal region about which less detailed images, or sub-images, are formed. In a preferred embodiment, sets of images or sub-images form levels of a hierarchy, and the wavelet encodings of the images or sub-images are decoded at rates associated with each level of the hierarchy. A single image may be partitioned into sub-images, or regions, that form each level of the hierarchy, or independent images may be arranged in a hierarchical manner, and subsequently rendered using a hierarchy of wavelet decoding schemes. The hierarchy can be developed at a remote site, and a hierarchical wavelet encoding can be transmitted to a local site, so that the hierarchical foveation effect can be rendered while the details of the lower levels of the hierarchy are being communicated.